package 二叉搜索树中的众数;

import java.util.*;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 二叉搜索树中的众数
 * @date 2022/11/6 16:25
 */
public class Demo501 {
    //======方法一参数
    static HashMap<Integer,Integer>  hash=new HashMap<>();
    //======方法二参数
    //中序遍历，记录前一个元素节点
    static TreeNode pre  =null;
    //记录当前节点的总个数
    static  int   count  =0;
    //记录最大节点的总个数
    static  int   maxCount  =0;
    //保存结果集，最后转成数组返回
    static  List<Integer>   resList  =new ArrayList<>();
    public static void main(String[] args) {
        TreeNode root=new TreeNode(1);
        root.left=new TreeNode(2);
       // root.right=new TreeNode(2);
       // root.right.left=new TreeNode(2);
        //中序遍历二叉搜索树

        int[] mode = findMode1(root);
        for (int i : mode) {
            System.out.println(i);
        }
    }

    //超时了，建议用2
    public  static int[] findMode(TreeNode root) {


        if(root==null){
            return new int[]{};
        }
         findMode(root.left);
         hash.put(root.val,hash.getOrDefault(root.val,0)+1);
         findMode(root.right);
        Set<Map.Entry<Integer, Integer>> entries = hash.entrySet();
         PriorityQueue<Map.Entry<Integer,Integer>>  res=new PriorityQueue<>((s1,s0)->s0.getValue()-s1.getValue());

        for (Map.Entry<Integer, Integer> entry : entries) {
            res.add(entry);
        }
        Integer value = res.peek().getValue();
        List<Integer> resList=new ArrayList<>();
        for (Map.Entry<Integer, Integer> re : res) {
            if(re.getValue()==value){
                resList.add(re.getKey());
            }
        }
        //list直接转int数组只能用下面这种方法
        return resList.stream().mapToInt(s->s).toArray();
    }

    //Definition for a binary tree node.
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) {
            this.val = val;}
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public  static int[] findMode1(TreeNode root) {

        if(root==null){
            return resList.stream().mapToInt(s->s).toArray();
        }
        //中序遍历 左中右
        // 左
        findMode1(root.left);
        //中 如果前一个结点是null，证明此时是便利的第一个元素
        if(pre==null){
            count++;
         //前一个元素和当前元素相等。count++
        }else if(pre.val== root.val){
           count++;
         //前一个元素和当前元素不相等。重新赋值为1
        }else {
            count=1;
        }
        if(count==maxCount){
            resList.add(root.val);
        }
        if(count>maxCount){
            resList.clear();
            maxCount=count;
            resList.add(root.val);
        }
        pre=root;
        findMode1(root.right);
        //list直接转int数组只能用下面这种方法
        return resList.stream().mapToInt(s->s).toArray();
    }
}
